This invention relates to circuit-based communication networks, such as, an optical switch or optical cross connect network, an ATM network, a Frame Relay network, a network of MPLS (Multi-Protocol Label Switching) enabled label switched routers, a network of Lambda (optical wavelength) routers, to name a few. In all such networks, circuits are provisioned between pairs of switches and numerous classes of services are carried on these circuits. Certain classes of circuits can be given preferential treatment over others. For example, there may be two classes of service—Premium and Basic—and Premium service circuits may receive priority treatment over any Basic service circuit.
These communication networks also consist of a number of switches which are connected by communication links. There could be multiple links between a given pair of switches and not every pair of switches needs to be connected to each other. Links could be of various sizes that are generally expressed in bandwidth units such as DS3, OC3, OC12, OC48, to name a few.
All these networks use routing and signaling protocols to automate a variety of functions, such as, for example, self-discovery of network resources, construction and maintenance of an identical link-state database of routing information across all switches (within an “Area”, “Peer Group,” etc.), automatic provisioning and restoration of circuits, determination of paths for provisioning and restoration of circuits, detection of network failure conditions, flooding of information related to any change in the state of the network to all switches, including failures of switches and links, change in available bandwidth on a link, to name a few.
The routing and signaling protocols, including OSPF, MPLS, PNNI, etc. and variants of these standard protocols, have been adapted to specific networks or applications.
These networks are characterized by the fact that the intelligence is distributed in every switch and is not centralized in one or more central locations. Typically, all switches run the same set of protocols although the functions performed by the switches may vary somewhat based on how switches are used. For example, “border switches” in an OSPF domain have greater functionality than other switches. Thus, the switches while employing the same or similar protocols operate independently of each other. Any co-ordination of activities between switches is done by sending messages to each other in ways prescribed by the routing and signaling protocols.
Communication circuits are established over a path or a sequence of links and switches through the network. Many of the current routing protocols always pick the shortest path with available capacity. Ties between equally short paths are typically broken in fixed order but could employ many known methods to make the choice.
While the routing protocols aim at disseminating network state information throughout the network in a timely fashion, this process also uses up valuable processing resources to formulate the routing messages and to send them out, as well as to assimilate the information that is received from the routing messages. Consequently, there is a trade-off between the rate at which routing messages are sent with updated network information, and the amount of processing resources devoted to process just the routing messages. In order to address this concern various timers are used by the routing protocols (as well as the signaling protocols) to control the rate at which these messages are sent. For example, updates of available bandwidth on a link may be sent no more than once every second, and therefore, the routing information may not be completely up to date. This is particularly true when a number of network events happen in a short amount of time, as is typically the case during a network failure involving the release and restoration of many circuits.
Also, in any large network failure scenario when multiple circuits are affected, there will be multiple switches that are source switches to these failed circuits. These switches initiate restoration in a “distributed” fashion, that is, without any co-ordination between the various switches. It is also well established that restoration for a failed circuit starts as soon as the source switch receives a release message for that circuit. Furthermore, the switches invoke the same algorithm for obtaining restoration paths and generally have identical link-state routing databases on which this path is calculated.
The source switch sets up a circuit for service or restoration using the signaling protocol. A setup message is sent out along the selected path of the circuit. Each switch in the path checks to see if the requested resources are available and then allocates the resources to the circuit. If all switches are able to allocate the resources then the setup succeeds otherwise it fails. An unsuccessful setup attempt typically results in a crankback to the source switch that then tries to set the circuit up on a different path.
As is well known in the prior art that the same Dijkstra implementation runs in every switch on identical link-state routing databases. There may be multiple links available to restore circuits between a pair of switches. The Dijkstra implementation breaks ties in a fixed manner always picking the same link. These facts together mean that different switches, and even different restoring circuits on the same switch, pick restoration paths that may contain the same selected link whenever there is a choice between equal weight links. Consequently, when many circuits fail, their restoration paths contain the same link between a pair of nodes, even though there may be several parallel links available. Hence, only some of the circuits will be able to restore before the available bandwidth is exhausted on the targeted link and the rest will crank back. Further, the routing updates as circuits restore may be delayed, and so all switches may pick the same link the next time they calculate the restoration path. Thus, there is need for a method that selects more than one link whenever there are several links between a pair of switches for calculating restoration paths, but continues to select just one link for service provisioning.
However, this invention overcomes the problems of the prior art. The invention works to restore services in a network. More particularly, the invention encompasses a scheme for randomized selection of equal cost links during restoration in a communication network. This leads to an efficient process for all service restoration.